{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find Nearest Point That Has the Same X or Y Coordinate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nearestValidPoint"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找到最近的有相同 X 或 Y 坐标的点"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个整数&nbsp;<code>x</code> 和&nbsp;<code>y</code>&nbsp;，表示你在一个笛卡尔坐标系下的&nbsp;<code>(x, y)</code>&nbsp;处。同时，在同一个坐标系下给你一个数组&nbsp;<code>points</code>&nbsp;，其中&nbsp;<code>points[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;表示在&nbsp;<code>(a<sub>i</sub>, b<sub>i</sub>)</code>&nbsp;处有一个点。当一个点与你所在的位置有相同的 <code>x</code> 坐标或者相同的 <code>y</code> 坐标时，我们称这个点是 <b>有效的</b>&nbsp;。</p>\n",
    "\n",
    "<p>请返回距离你当前位置&nbsp;<strong>曼哈顿距离</strong>&nbsp;最近的&nbsp;<strong>有效</strong>&nbsp;点的下标（下标从 <strong>0</strong> 开始）。如果有多个最近的有效点，请返回下标&nbsp;<strong>最小</strong>&nbsp;的一个。如果没有有效点，请返回&nbsp;<code>-1</code>&nbsp;。</p>\n",
    "\n",
    "<p>两个点 <code>(x<sub>1</sub>, y<sub>1</sub>)</code>&nbsp;和 <code>(x<sub>2</sub>, y<sub>2</sub>)</code>&nbsp;之间的 <strong>曼哈顿距离</strong>&nbsp;为&nbsp;<code>abs(x<sub>1</sub> - x<sub>2</sub>) + abs(y<sub>1</sub> - y<sub>2</sub>)</code>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>x = 3, y = 4, points = [[1,2],[3,1],[2,4],[2,3],[4,4]]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>所有点中，[3,1]，[2,4] 和 [4,4] 是有效点。有效点中，[2,4] 和 [4,4] 距离你当前位置的曼哈顿距离最小，都为 1 。[2,4] 的下标最小，所以返回 2 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>x = 3, y = 4, points = [[3,4]]\n",
    "<b>输出：</b>0\n",
    "<b>提示：</b>答案可以与你当前所在位置坐标相同。</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>x = 3, y = 4, points = [[2,3]]\n",
    "<b>输出：</b>-1\n",
    "<b>解释：</b>没有 有效点。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= points.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>points[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x, y, a<sub>i</sub>, b<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-nearest-point-that-has-the-same-x-or-y-coordinate](https://leetcode.cn/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-nearest-point-that-has-the-same-x-or-y-coordinate](https://leetcode.cn/problems/find-nearest-point-that-has-the-same-x-or-y-coordinate/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n4\\n[[1,2],[3,1],[2,4],[2,3],[4,4]]', '3\\n4\\n[[3,4]]', '3\\n4\\n[[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        idx,minx=0,math.inf\n",
    "        for i in points:\n",
    "            if i[0]==x or i[1]==y:\n",
    "                minx=min(minx,abs(i[0]-x)+abs(i[1]-y))\n",
    "        for i in range(len(points)):\n",
    "            if (points[i][0]==x or points[i][1]==y) and abs(points[i][0]-x)+abs(points[i][1]-y)==minx:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        dis = float('inf')\n",
    "        ans = -1\n",
    "        for idx, point in enumerate(points):\n",
    "            if point[0] == x or point[1] == y:\n",
    "                if abs(point[0] - x) + abs(point[1] - y) < dis:\n",
    "                    dis = abs(point[0] - x) + abs(point[1] - y)\n",
    "                    ans = idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points) #点的数量\n",
    "        min_distance = 10e4\n",
    "\n",
    "        for i in range(n):\n",
    "            if points[i][0] == x:\n",
    "                distance = abs(points[i][1] - y)\n",
    "                if distance < min_distance:\n",
    "                    min_distance = distance\n",
    "                    position_out = i\n",
    "            if points[i][1] == y:\n",
    "                distance = abs(points[i][0] - x)\n",
    "                if distance < min_distance:\n",
    "                    min_distance = distance\n",
    "                    position_out = i\n",
    "\n",
    "        if min_distance == 10e4:\n",
    "            position_out = -1\n",
    "\n",
    "        return position_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res, distance = -1, inf\n",
    "        for index, point in enumerate(points):\n",
    "            i, j = point\n",
    "            if i == x or j == y:\n",
    "                tmp = abs(i-x) + abs(j-y)\n",
    "                if tmp < distance:\n",
    "                    res = index\n",
    "                    distance = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        a = 65536\n",
    "        m = -1\n",
    "        for n,(i,j) in enumerate(points):\n",
    "            if i == x or j == y:\n",
    "                b = abs(x - i) + abs(y - j)\n",
    "                if b < a:\n",
    "                    a = b\n",
    "                    m = n\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        length = len(points)\n",
    "        temp_dict = dict()\n",
    "        distance_list = []\n",
    "        for i in range(length):\n",
    "            if points[i][0]==x or points[i][1]==y:\n",
    "                distance = abs(points[i][0]-x)+ abs(points[i][1]-y)\n",
    "                if distance not in temp_dict:\n",
    "                    temp_dict[distance] = i\n",
    "                    distance_list.append(distance)\n",
    "        distance_list.sort()\n",
    "        return temp_dict[distance_list[0]] if distance_list else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        dis =0\n",
    "        m=1e9\n",
    "        validList = []\n",
    "        diss = []\n",
    "        for i in points:\n",
    "            if i[0]==x:\n",
    "                dis = abs(i[1]-y)\n",
    "                validList.append(i)\n",
    "                diss.append(dis)\n",
    "            elif i[1]==y:\n",
    "                dis = abs(i[0]-x)\n",
    "                validList.append(i)\n",
    "                diss.append(dis)\n",
    "\n",
    "        if len(validList)==0:\n",
    "            return -1\n",
    "        # print(min(diss))\n",
    "        r = points.index(validList[diss.index(min(diss))])\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res = -1\n",
    "        cur = sys.maxsize\n",
    "        for i in range(len(points)) :\n",
    "            if x == points[i][0] or y == points[i][1] :\n",
    "                dist = abs(x - points[i][0]) + abs(y - points[i][1]);\n",
    "                if dist < cur :\n",
    "                    cur = dist\n",
    "                    res = i\n",
    "\n",
    "        return res    \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points) #点的数量\n",
    "        min_distance = 10e4\n",
    "\n",
    "        for i in range(n):\n",
    "            if points[i][0] == x:\n",
    "                distance = abs(points[i][1] - y)\n",
    "                if distance < min_distance:\n",
    "                    min_distance = distance\n",
    "                    position_out = i\n",
    "            if points[i][1] == y:\n",
    "                distance = abs(points[i][0] - x)\n",
    "                if distance < min_distance:\n",
    "                    min_distance = distance\n",
    "                    position_out = i\n",
    "\n",
    "        if min_distance == 10e4:\n",
    "            position_out = -1\n",
    "        return position_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        tx = ty = 10 ** 9\n",
    "        ret = -1\n",
    "        for i, (a, b) in enumerate(points):\n",
    "            if (x == a or y == b) and abs(x - a) + abs(y - b) < abs(x - tx) + abs(y - ty):\n",
    "                # print(x,y, a,b, tx, ty, abs(x - a) + abs(y - b), abs(x - tx) + abs(y - ty))\n",
    "                ret = i\n",
    "                tx, ty = a, b\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        s = float(\"INF\")\n",
    "        ans = -1\n",
    "        for i in range(len(points)):\n",
    "            m, n = points[i]\n",
    "            if m == x or n == y:\n",
    "                d = abs(m - x) + abs(n - y)\n",
    "                if d < s:\n",
    "                    ans = i\n",
    "                    s = d\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        best, bestid = float(\"inf\"), -1\n",
    "        for i, (px, py) in enumerate(points):\n",
    "            if x == px:\n",
    "                if (dist := abs(y - py)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "            elif y == py:\n",
    "                if (dist := abs(x - px)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "        \n",
    "        return bestid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        minx=math.inf\n",
    "        for i in points:\n",
    "            if i[0]==x or i[1]==y:\n",
    "                minx=min(minx,abs(i[0]-x)+abs(i[1]-y))\n",
    "        for i in range(len(points)):\n",
    "            if (points[i][0]==x or points[i][1]==y) and abs(points[i][0]-x)+abs(points[i][1]-y)==minx:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        dis = float('inf')\n",
    "        ans = -1\n",
    "        for idx, point in enumerate(points):\n",
    "            if point[0] == x or point[1] == y:\n",
    "                if abs(point[0] - x) + abs(point[1] - y) < dis:\n",
    "                    dis = abs(point[0] - x) + abs(point[1] - y)\n",
    "                    ans = idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        dis = float('inf')\n",
    "        ans = -1\n",
    "        for idx, (px, py) in enumerate(points):\n",
    "            if x == px:\n",
    "                if abs(y - py) < dis:\n",
    "                    dis = abs(y - py)\n",
    "                    ans = idx\n",
    "            elif y == py:\n",
    "                if abs(x - px) < dis:\n",
    "                    dis = abs(x - px)\n",
    "                    ans = idx\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res, distance = -1, inf\n",
    "        for index, point in enumerate(points):\n",
    "            i, j = point\n",
    "            if i == x or j == y:\n",
    "                tmp = abs(i-x) + abs(j-y)\n",
    "                if tmp < distance:\n",
    "                    res = index\n",
    "                    distance = tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res = -1\n",
    "        minll = inf\n",
    "        for i,[a,b] in enumerate(points):\n",
    "            if a == x or b == y:\n",
    "                ll = abs(a-x)+abs(b-y)\n",
    "                if ll <minll:\n",
    "                    res = i\n",
    "                    minll = ll\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        flag = -1\n",
    "        for i, (a, b) in enumerate(points):\n",
    "            if x==a or y==b:\n",
    "                data=abs(x-a)+abs(y-b)\n",
    "                flag=i\n",
    "                break\n",
    "        for i, (a,b) in enumerate(points):\n",
    "            if  x==a and y==b:  #找到相同点直接返回\n",
    "                flag=i\n",
    "                break\n",
    "            elif x==a or y==b:  #不是同一个点但是有效点\n",
    "                if data>abs(x-a)+abs(y-b): #比上一个有效点近，返回最近的\n",
    "                    flag=i\n",
    "                    data=abs(x-a)+abs(y-b)\n",
    "        return flag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        best, bestid = float(\"inf\"), -1\n",
    "        for i, (px, py) in enumerate(points):\n",
    "            if x == px:\n",
    "                if (dist := abs(y - py)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "            elif y == py:\n",
    "                if (dist := abs(x - px)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "        \n",
    "        return bestid\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        target_index, minimum = -1, float('inf')\n",
    "        for index, (px, py) in enumerate(points):\n",
    "            if px == x or py == y:\n",
    "                dis = abs(x - px) + abs(y - py)\n",
    "                if dis < minimum:\n",
    "                    minimum = dis\n",
    "                    target_index = index\n",
    "        return target_index\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        best,bestid = float(\"inf\"),-1\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0]==x or points[i][1]==y:\n",
    "                distance = abs(x-points[i][0])+abs(y-points[i][1])\n",
    "                if distance<best:\n",
    "                    best = distance\n",
    "                    bestid = i\n",
    "        return bestid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        minDist = float(\"inf\")\n",
    "        ans = -1\n",
    "        for ind, point in enumerate(points):\n",
    "            if point[0] == x or point[1] == y:\n",
    "                dist = abs(point[0] - x) + abs(point[1] - y)\n",
    "                if dist < minDist:\n",
    "                    minDist = dist\n",
    "                    ans = ind\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        s=[tuple(i) for i in points if i[0]==x or i[1]==y]\n",
    "        if len(s)==0:\n",
    "            return -1\n",
    "        else:\n",
    "            t=sorted(s,key=lambda i:abs(i[0]-x)+abs(i[1]-y))\n",
    "            return points.index(list(t[0]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:      \n",
    "        hasmap = {}\n",
    "        for i in range(len(points)):\n",
    "            if x == points[i][0] or y == points[i][1]:\n",
    "                p = abs(points[i][0] + points[i][1] - x - y)\n",
    "                if p not in hasmap:\n",
    "                    hasmap[p] = i\n",
    "        \n",
    "        if len(hasmap) == 0:\n",
    "            return -1\n",
    "        else:\n",
    "            return hasmap[min(hasmap.keys())]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        tmp = 1e9\n",
    "        ans = -1\n",
    "        for i in range(len(points)):\n",
    "            if x == points[i][0] or y == points[i][1]:\n",
    "                if abs(x - points[i][0]) + abs(y - points[i][1]) < tmp:\n",
    "                    tmp = abs(x - points[i][0]) + abs(y - points[i][1])\n",
    "                    ans = i\n",
    "        return ans\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        candidates = []\n",
    "        for i, p in enumerate(points):\n",
    "            # print(i,p)\n",
    "            x_ = p[0]\n",
    "            y_ = p[1]\n",
    "            if (x_ == x) or (y_ == y):\n",
    "                candidates.append([i,p])\n",
    "        if len(candidates) == 0:\n",
    "            return -1\n",
    "        # print(candidates)\n",
    "        res = []\n",
    "        for i,p in candidates:\n",
    "            dist = abs(p[0]-x)+abs(p[1]-y)\n",
    "            res.append([dist,i])\n",
    "        # print(res)\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        res=list(filter(lambda x:x[0]==res[0][0],res))\n",
    "        res.sort(key=lambda x:x[1])\n",
    "        # print(res)\n",
    "        return res[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        best, bestid = float(\"inf\"), -1\n",
    "        for i, (px, py) in enumerate(points):\n",
    "            if x == px:\n",
    "                if (dist := abs(y - py)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "            elif y == py:\n",
    "                if (dist := abs(x - px)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "        \n",
    "        return bestid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res = -1\n",
    "        dis = inf\n",
    "        for i in range(len(points)):\n",
    "            px, py = points[i]\n",
    "            if px == x or py == y:\n",
    "                new_dis = abs(px - x) + abs(py - y)\n",
    "                if new_dis < dis:\n",
    "                    dis = new_dis\n",
    "                    res = i\n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res = 10000\n",
    "        minp = 0\n",
    "        count =0\n",
    "        j=-1\n",
    "        for point in points:\n",
    "            j +=1\n",
    "            if point[0] == x and point[1] == y:\n",
    "                return j\n",
    "            elif point[0] == x or point[1] == y:\n",
    "                juli = abs(point[0] - x) + abs(point[1] - y)\n",
    "                if juli < res :\n",
    "                    res = juli \n",
    "                    minp = j\n",
    "                count =1\n",
    "        if count == 0:\n",
    "            return -1\n",
    "            \n",
    "        return minp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        result = None\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                s = abs(points[i][0]-x)+abs(points[i][1]-y)\n",
    "                if result == None:\n",
    "                    result = i\n",
    "                    a = s\n",
    "                if s < a:\n",
    "                    result = i\n",
    "                    a = s\n",
    "                    continue\n",
    "                else:\n",
    "                    continue\n",
    "        if result == None:\n",
    "            return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        mindis = 1000000\n",
    "        resindex= -1\n",
    "        for i,each_list in enumerate(points):\n",
    "            if (x == each_list[0] or y == each_list[1]) and abs(x-each_list[0])+abs(y-each_list[1]) < mindis:\n",
    "                mindis = abs(x-each_list[0])+abs(y-each_list[1])\n",
    "                resindex = i\n",
    "        return resindex"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        d, min_distance = collections.defaultdict(int), float('inf')\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                min_distance = min(min_distance, abs(points[i][0] - x) + abs(points[i][1] - y))\n",
    "                if min_distance not in d:\n",
    "                    d[min_distance] = i\n",
    "\n",
    "        return d[min_distance] if d else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        found = -1\n",
    "        distance = 99999\n",
    "        for i, point in enumerate(points):\n",
    "            if point[0] != x and point[1] != y:\n",
    "                continue\n",
    "            dist = abs(point[0] - x) + abs(point[1] - y)\n",
    "            if dist < distance:\n",
    "                distance = dist\n",
    "                found = i\n",
    "\n",
    "        return found "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        min_distance = float('inf')\n",
    "        nearest_point_index = -1\n",
    "        \n",
    "        for i, (px, py) in enumerate(points):\n",
    "            if px == x or py == y:\n",
    "                distance = abs(px - x) + abs(py - y)\n",
    "                if distance < min_distance:\n",
    "                    min_distance = distance\n",
    "                    nearest_point_index = i\n",
    "                    \n",
    "        return nearest_point_index\n",
    "\n",
    "# 测试代码\n",
    "if __name__ == '__main__':\n",
    "    s = Solution()\n",
    "    \n",
    "    print(s.nearestValidPoint(3, 4, [[1,2],[3,1],[2,4],[2,3],[4,4]]))  # 应该返回 2\n",
    "    print(s.nearestValidPoint(3, 4, [[1,2],[2,3],[3,4]]))  # 应该返回 2\n",
    "    print(s.nearestValidPoint(3, 4, [[2,3]]))  # 应该返回 0\n",
    "    print(s.nearestValidPoint(3, 4, [[1,2],[2,2],[2,3]]))  # 应该返回 2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        minDistance, minIndx = inf, inf \n",
    "        for idx, (px, py) in enumerate(points):\n",
    "            if px == x or py == y:\n",
    "                curDistance = abs(px - x) + abs(py - y)\n",
    "                # print(minDistance,curDistance, minIdx,px, py, idx)\n",
    "                if curDistance < minDistance:\n",
    "                    minDistance = curDistance\n",
    "                    minIndx = idx\n",
    "        return minIndx if minIndx != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        r = -1\n",
    "        mi = float('inf')\n",
    "        for i in range(len(points)):\n",
    "            a, b = points[i]\n",
    "            if a == x or b == y:\n",
    "                t = abs(a-x)+abs(b-y)\n",
    "                if t < mi:\n",
    "                    r, mi = i, t\n",
    "        return r\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        candidates = []\n",
    "        for i, p in enumerate(points):\n",
    "            # print(i,p)\n",
    "            x_ = p[0]\n",
    "            y_ = p[1]\n",
    "            if (x_ == x) or (y_ == y):\n",
    "                candidates.append([i,p])\n",
    "        if len(candidates) == 0:\n",
    "            return -1\n",
    "        print(candidates)\n",
    "        res = []\n",
    "        for i,p in candidates:\n",
    "            dist = abs(p[0]-x)+abs(p[1]-y)\n",
    "            res.append([dist,i])\n",
    "        print(res)\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        res=list(filter(lambda x:x[0]==res[0][0],res))\n",
    "        res.sort(key=lambda x:x[1])\n",
    "        print(res)\n",
    "        return res[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        return min([(abs(x - i) + abs(y - j), index) for index, (i, j) in enumerate(points) if i == x or j == y], default=(-1, -1))[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        a,min =-1,1000000\n",
    "        for i,(b,c) in enumerate(points):\n",
    "            if (x==b) or (y==c):\n",
    "                d=abs(b-x)+abs(c-y)\n",
    "                if min>d:\n",
    "                    a,min=i,d\n",
    "        return a\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "\n",
    "        temp_list = []\n",
    "        for i in range(len(points)):\n",
    "            if x == points[i][0] or y == points[i][1]:\n",
    "                temp_list.append(i)\n",
    "\n",
    "        if not temp_list:\n",
    "            return -1\n",
    "        elif len(temp_list) ==1:\n",
    "\n",
    "            return temp_list[0]\n",
    "\n",
    "        else:\n",
    "            point_dict = [[] for _ in range(len(temp_list))]\n",
    "            for j in range(len(temp_list)):\n",
    "                distance = abs(x - points[temp_list[j]][0]) + abs(y - points[temp_list[j]][1])\n",
    "                point_dict[j].extend([temp_list[j], distance])\n",
    "            point_dict.sort(key = lambda x: (x[1], x[0]))\n",
    "\n",
    "            return point_dict[0][0]\n",
    "\n",
    "\n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        best,bestid = float(\"inf\"),-1\n",
    "        for i,(px,py) in enumerate(points):\n",
    "            if x==px:\n",
    "                if(dist:=abs(y-py))<best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "            elif y==py:\n",
    "                if(dist:= abs(x-px))<best:\n",
    "                    best=dist\n",
    "                    bestid =i\n",
    "        return bestid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        min_idx = -1\n",
    "        min_dist = 10e4\n",
    "        for idx, (x_, y_) in enumerate(points):\n",
    "            if x == x_ and y == y_:\n",
    "                return idx\n",
    "            if x == x_ or y == y_:\n",
    "                curr_dist = abs(x - x_) + abs(y - y_)\n",
    "                if curr_dist < min_dist:\n",
    "                    min_idx = idx\n",
    "                    min_dist = curr_dist\n",
    "        return min_idx\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        best, bestid = float(\"inf\"), -1\n",
    "        for i, (px, py) in enumerate(points):\n",
    "            if x == px:\n",
    "                if (dist := abs(y - py)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "            elif y == py:\n",
    "                if (dist := abs(x - px)) < best:\n",
    "                    best = dist\n",
    "                    bestid = i\n",
    "        \n",
    "        return bestid\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        n = len(points)\n",
    "        res = inf\n",
    "        ans = -1\n",
    "        for i in range(n):\n",
    "            a, b = points[i]\n",
    "            if x == a or y == b:\n",
    "                cur = abs(x-a)+abs(y-b)\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "                    ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        minDist = 10000\n",
    "        inx = 0\n",
    "        n = len(points)\n",
    "        for i in range(n):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                if abs(x-points[i][0]) + abs(y-points[i][1]) < minDist:\n",
    "                    minDist = abs(x-points[i][0]) + abs(y-points[i][1])\n",
    "                    inx = i\n",
    "        if minDist == 10000:\n",
    "            inx = -1\n",
    "\n",
    "        return inx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        res = -1\n",
    "        dis = inf\n",
    "        for i in range(len(points)):\n",
    "            px, py = points[i]\n",
    "            if px == x or py == y:\n",
    "                new_dis = abs(px - x) + abs(py - y)\n",
    "                if new_dis < dis:\n",
    "                    dis = new_dis\n",
    "                    res = i\n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        ans,distance=-1,float('inf')\n",
    "        for i,(a,b) in enumerate(points):\n",
    "            if a==x or b==y:\n",
    "                d = abs(a-x)+abs(b-y)\n",
    "                if d<distance:\n",
    "                    distance=d\n",
    "                    ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        result = None\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                s = abs(points[i][0]-x)+abs(points[i][1]-y)\n",
    "                if result == None:\n",
    "                    result = i\n",
    "                    a = s\n",
    "                if s < a:\n",
    "                    result = i\n",
    "                    a = s\n",
    "                    continue\n",
    "                else:\n",
    "                    continue\n",
    "        if result == None:\n",
    "            return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        ans = -1\n",
    "        min_dis = 200001\n",
    "        for index, point in enumerate(points):\n",
    "            if x == point[0] or y == point[1]:\n",
    "                dis = abs(x - point[0]) + abs(y - point[1])\n",
    "                if dis < min_dis:\n",
    "                    ans = index\n",
    "                    min_dis = dis\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        min_d = 10**5\n",
    "        res = -1\n",
    "        for i in range(0,len(points)):\n",
    "            if x == points[i][0] or y == points[i][1]:\n",
    "                d = abs(x-points[i][0]) + abs(y-points[i][1])\n",
    "                if d < min_d:\n",
    "                    res = i\n",
    "                    min_d = d\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        fh = -1\n",
    "        a = float('inf') \n",
    "        for i, (j, k) in enumerate(points):\n",
    "            if x == j or y == k:\n",
    "                jl = abs(x-j) + abs(y-k)\n",
    "                if jl < a:\n",
    "                    a = jl\n",
    "                    fh = i\n",
    "        return fh\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        num = 10000\n",
    "        ans = -1\n",
    "        for i, point in enumerate(points):\n",
    "            if point[0] == x or point[1] == y:\n",
    "                k = abs(point[0] - x) +  abs(point[1] - y)\n",
    "                if k < num:\n",
    "                    num = k\n",
    "                    ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        candidates = []\n",
    "        for i, p in enumerate(points):\n",
    "            # print(i,p)\n",
    "            x_ = p[0]\n",
    "            y_ = p[1]\n",
    "            if (x_ == x) or (y_ == y):\n",
    "                candidates.append([i,p])\n",
    "        if len(candidates) == 0:\n",
    "            return -1\n",
    "        print(candidates)\n",
    "        res = []\n",
    "        for i,p in candidates:\n",
    "            dist = abs(p[0]-x)+abs(p[1]-y)\n",
    "            res.append([dist,i])\n",
    "        print(res)\n",
    "        res.sort(key=lambda x:x[0])\n",
    "        res=[k for k in res if k[0]==res[0][0]]\n",
    "        # res.sort(key=lambda x:x[1])\n",
    "        print(res)\n",
    "        return res[0][1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        # 直接遍历\n",
    "        '''\n",
    "直接遍历 points 数组，对于 points[i]，如果 points[i][0]=x 或者 points[i][1]=y，则说明 points[i] 是有效点\n",
    "\n",
    "计算曼哈顿距离，更新最小距离和最小距离的下标\n",
    "        '''\n",
    "        # 下标\n",
    "        ans = -1\n",
    "        mi = inf\n",
    "        for i, (a,b) in enumerate(points):\n",
    "            if a == x or b == y:\n",
    "                d = abs(a - x) + abs(b - y)\n",
    "                if mi > d:\n",
    "                    ans, mi = i, d\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        ans,dis = -1,float('inf')\n",
    "        for idx in range(len(points)):\n",
    "            if points[idx][0] == x or points[idx][1] == y:\n",
    "                if abs(points[idx][0]-x) + abs(points[idx][1]-y) < dis:\n",
    "                    dis = abs(points[idx][0]-x) + abs(points[idx][1]-y)\n",
    "                    ans = idx\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        d, min_distance = collections.defaultdict(int), float('inf')\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                min_distance = min(min_distance, abs(points[i][0] - x) + abs(points[i][1] - y))\n",
    "                if min_distance not in d:\n",
    "                    d[min_distance] = i\n",
    "\n",
    "        return d[min_distance] if d else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        result = None\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                s = abs(points[i][0]-x)+abs(points[i][1]-y)\n",
    "                if result == None:\n",
    "                    result = i\n",
    "                    a = s\n",
    "                if s < a:\n",
    "                    result = i\n",
    "                    a = s\n",
    "                    continue\n",
    "                else:\n",
    "                    continue\n",
    "        if result == None:\n",
    "            return -1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "\n",
    "        min_d = 10**8\n",
    "        res = -1\n",
    "        i = 0 \n",
    "        for a,b in points:\n",
    "            if a==x or b==y:\n",
    "                d = abs(x-a)+abs(y-b)\n",
    "                if d<min_d:\n",
    "                    min_d = d \n",
    "                    res = i \n",
    "            i += 1\n",
    "        \n",
    "        return res \n",
    "                    \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        result = []\n",
    "        for i in range(len(points)):\n",
    "            temp = {}\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                distance = abs(points[i][0] - x) + abs(points[i][1] - y)\n",
    "                temp['distance'] = distance\n",
    "                temp['index'] = i\n",
    "                result.append(temp)\n",
    "        if result:\n",
    "            result.sort(key=lambda x:x['distance'])\n",
    "            return result[0]['index']\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        import sys\n",
    "        \"\"\"\n",
    "        :param x:int\n",
    "        :param y:int\n",
    "        :param points: List[List[int]]\n",
    "        :return: int\n",
    "        \"\"\"\n",
    "        min_dist = sys.maxsize\n",
    "        ans = sys.maxsize\n",
    "        for index in range(len(points)):\n",
    "            if points[index][0] == x or points[index][1] == y:\n",
    "                dist = abs(points[index][1] - y) + abs(points[index][0] - x)\n",
    "                if dist < min_dist:\n",
    "                    min_dist = dist\n",
    "                    ans = index\n",
    "        return -1 if ans == sys.maxsize else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nearestValidPoint(self, x: int, y: int, points: List[List[int]]) -> int:\n",
    "        d, min_distance = collections.defaultdict(int), float('inf')\n",
    "\n",
    "        for i in range(len(points)):\n",
    "            if points[i][0] == x or points[i][1] == y:\n",
    "                min_distance = min(min_distance, abs(points[i][0] - x) + abs(points[i][1] - y))\n",
    "                if min_distance == 0:\n",
    "                    return i\n",
    "                if min_distance not in d:\n",
    "                    d[min_distance] = i\n",
    "                    \n",
    "\n",
    "        return d[min_distance] if d else -1"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
